﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0067_FindAnagrams : IAlgorithm
    {
        // 438. 找到字符串中所有字母异位词

        // 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
        // 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

        // 提示:
        //  1 <= s.length, p.length <= 3 * 10^4
        //  s 和 p 仅包含小写字母

        public void Test()
        {
            // 算法参数定义
            string s = "aa", p = "bb";

            // 算法执行与打印
            var res = FindAnagrams(s, p);
            foreach (var item in res)
            {
                Console.Write(item + " ");
            }
        }

        // 算法
        // string s = "cbaebabacd", p = "abc";
        public IList<int> FindAnagrams(string s, string p)
        {
            var res = new List<int>();
            // 若s长度小于p，s中必然没有p的异位词
            if (s.Length < p.Length)
                return res;
            int[] charCnt = new int[26];
            // 记录各字符在p长度下出现情况，s对应字符累加，p对应字符递减
            for (int i = 0; i < p.Length; i++)
            {
                charCnt[s[i] - 'a']++;
                charCnt[p[i] - 'a']--;
            }
            var diff = 0;
            // 遍历字符累计数组，各字符绝对值之和就是两者的差异
            for (int i = 0; i < 26; i++)
            {
                diff += Math.Abs(charCnt[i]);
            }
            // 无差异直接添加
            if (diff == 0)
                res.Add(0);
            // 从p长度开始，遍历s字符串
            for (int i = p.Length; i < s.Length; i++)
            {
                // 进窗口的字符索引
                var enCharVal = s[i] - 'a';
                // 当原有值小于0，进入滑动窗口，只会减少差异
                if (charCnt[enCharVal] < 0)
                    diff--;
                // 反则增加差异
                else
                    diff++;
                charCnt[enCharVal]++;
                // 出窗口的字符索引
                var deCharVal = s[i - p.Length] - 'a';
                // 当原有值大于0，退出滑动窗口，只会减少差异
                if (charCnt[deCharVal] > 0)
                    diff--;
                // 反则增加差异
                else
                    diff++;
                charCnt[deCharVal]--;
                // 无差异直接添加
                if (diff == 0)
                    res.Add(i - p.Length + 1);
            }
            return res;
        }
    }
}
